//https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
// 我的解法是：1，只有在遇到‘[’才会去压栈；2.如果遇到]，那么就把stack中top的元素取出来，包含了num与str，组成一个大的str，同时pop这个数据；
//3.此时，要看栈里面是否还盛数据，如果有，那么将上一步组合的大的str加到当前的头部元素的str后面；否则，直接加到res后面；

// 官方解法：我觉得也很好，遇到一个cur-num就处理一个，多的不处理；
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <climits>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    string decodeString(string s) {
        std::string res="";
        if(s.empty()) return res;
        std::stack<std::pair<int,string>> stack;
        int cur_num=0;
        for(size_t i=0;i<s.size();++i){
            if(stack.empty() &&isdigit(s[i])){
                cur_num=cur_num*10+s[i]-'0';
            }else if(stack.empty() && s[i]=='[') {
                stack.push({cur_num,""});
                cur_num=0;
            }else if (stack.empty() &&isalpha(s[i])) {
                res+=s[i];
            }
            else if (!stack.empty() && s[i]=='['){
                stack.push({cur_num,""});
                cur_num=0;
            }else if (!stack.empty() && s[i]==']'){
                cur_num=0;
                auto cur_pair=stack.top();
                int cur_num=cur_pair.first;
                std::string cur_str=cur_pair.second;
                std::string sum_str="";
                stack.pop();
                while(cur_num--) {
                   sum_str+=cur_str;
                }
                if(!stack.empty()){
                    stack.top().second+=sum_str;
                }else{
                    res+=sum_str;
                }
            }else if(!stack.empty() && isdigit(s[i])){
                cur_num=cur_num*10+s[i]-'0';
            }else if(!stack.empty() && isalpha(s[i])) {
                stack.top().second+=s[i];
                cur_num=0;
            }
        }
        return res;
    }
};


class Solution {
public:
    string getDigits(string &s, size_t &ptr) {
        string ret = "";
        while (isdigit(s[ptr])) {
            ret.push_back(s[ptr++]);
        }
        return ret;
    }

    string getString(vector <string> &v) {
        string ret;
        for (const auto &s: v) {
            ret += s;
        }
        return ret;
    }

    string decodeString(string s) {
        vector <string> stk;
        size_t ptr = 0;

        while (ptr < s.size()) {
            char cur = s[ptr];
            if (isdigit(cur)) {
                // 获取一个数字并进栈
                string digits = getDigits(s, ptr);
                stk.push_back(digits);
            } else if (isalpha(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.push_back(string(1, s[ptr++])); 
            } else {
                ++ptr;
                vector <string> sub;
                while (stk.back() != "[") {
                    sub.push_back(stk.back());
                    stk.pop_back();
                }
                reverse(sub.begin(), sub.end());
                // 左括号出栈
                stk.pop_back();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = stoi(stk.back()); 
                stk.pop_back();
                string t, o = getString(sub);
                // 构造字符串
                while (repTime--) t += o; 
                // 将构造好的字符串入栈
                stk.push_back(t);
            }
        }

        return getString(stk);
    }
};